package 图.有向图;

import 抽象数据类型.Digraph;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-03
 */
public class 拓扑排序DFS {
    public static void main(String[] args) {
        int[] arr1 = {2, 1, 2, 3, 0};
        int[] arr2 = {1, 3, 3, 4, 4};
        Digraph G = new Digraph(arr1.length);
        G.addDigraph(arr1, arr2);
        Topological degrees = new Topological(G);
        for (Integer w : degrees.order) {
            System.out.println(w);
        }

    }
    public static class Topological {
        private Iterable<Integer> order;

        public Topological(Digraph g) {
            查找有向环.DirectedCycle cycle = new 查找有向环.DirectedCycle(g);
            if (!cycle.hasCycle()) {
                基于深度优先搜索的顶点排序.DepthFirstOrder dfs = new 基于深度优先搜索的顶点排序.DepthFirstOrder(g);
                order = dfs.reversePost();
            }
        }

        public Iterable<Integer> order() {
            return order;
        }
        public boolean isDAG() {
            return order != null;
        }


    }
}
